package leetcode.动态规划和贪心;

/**
 * 跳跃游戏 II
 *
 * https://leetcode-cn.com/problems/jump-game-ii/
 */
public class Test45跳跃游戏II {

    public static int jump2(int[] nums) {
        if (nums.length == 1 || nums[0] == 0)
            return 0;
        int cont = 0;
        int n = nums.length;
        int i = 0;
        int max = 0;
        while (max < n - 1) {
            cont++;
            int a = max;
            for (; i <= a; i++) {
                max = Math.max(max, i + nums[i]);
            }
        }
        return cont++;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
//        int[] nums = {0, 2};
//        int[] nums = {1, 2, 3};
//        int[] nums = {2,3,1};
//        int[] nums = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0};
        System.out.println(jump(nums));
    }

    /**
     * 贪心法求解，贪心策略是在每一步可走步长内，走最大前进的步数
     */
    public static int jump(int[] nums) {
        if (nums.length == 1 || nums[0] == 0)
            return 0;
        int index, maxLocation = 0;
        int step = 0, i = 0;
        while (i < nums.length) {
            // 如果能直接一步走到最后，直接步数+1结束
            if (i + nums[i] >= nums.length - 1) {
                step++;
                break;
            }
            maxLocation = 0;//每次都要初始化
            index = i + 1;//记录索引，最少前进1步
            for (int j = index; j <= nums[i] + i; j++) {//搜索最大步长内行走最远的那步
                if (maxLocation < nums[j] + j) {
                    maxLocation = nums[j] + j;//记录最大值
                    index = j;//记录最大值索引
                }
            }
            i = index;//直接走到能走最远的那步
            step++;//步长+1
        }
        return step;
    }
}
